package com.rran.study.algorithm.easy.day01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author yy
 * @Type Solution01.java
 * @Desc 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 * 输入：
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 输出：[3, 14.5, 11]
 * 解释：
 * 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 * 节点值的范围在32位有符号整数范围内。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020/9/3
 */
class Solution01 {

    public static void main(String[] args) {
        Solution01 solution = new Solution01();
        TreeNode t0 = new TreeNode(2147483647);
        TreeNode t1 = new TreeNode(2147483647);
        TreeNode t2 = new TreeNode(2147483647);
        TreeNode t3 = new TreeNode(15);
        TreeNode t4 = new TreeNode(7);
        t0.setLeft(t1);
        t0.setRight(t2);
//        t2.setLeft(t3);
//        t2.setRight(t4);
        List<Double> result = solution.averageOfLevels(t0);
        double[] array = new double[result.size()];

        //打印结果
        for (Double d : result) {
            System.out.println(d);
        }
    }

    private Map<Integer, Double> sumValMap = new HashMap<>();
    private Map<Integer, Integer> sumNumMap = new HashMap<>();


    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList();
        //树的层数
        int n = 1;
        //初始化根节点
        sumValMap.put(1, (double) root.getVal());
        sumNumMap.put(1, 1);
        //执行算法
        sumVal(root, 1);

        for (Integer key : sumValMap.keySet()) {
            Integer num = sumNumMap.get(key);
            result.add(((double) sumValMap.get(key) / num));
        }
        return result;
    }


    public void sumVal(TreeNode node, int n) {
        double leftVal = 0;
        double rightVal = 0;

        //左节点
        TreeNode left = node.getLeft();
        //右节点
        TreeNode right = node.getRight();

        if (left != null) {
            leftVal = left.getVal();
            sumVal(left, n + 1);
            storeSumNumMap(n + 1);
        }
        if (right != null) {
            rightVal = right.getVal();
            sumVal(right, n + 1);
            storeSumNumMap(n + 1);
        }
        if (left != null || right != null) {
            storeSumValMap(n + 1, leftVal + rightVal);
        }
    }

    public void storeSumValMap(int n, double val) {
        sumValMap.merge(n, val, Double::sum);
    }

    public void storeSumNumMap(int n) {
        sumNumMap.merge(n, 1, Integer::sum);
    }
}

